/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ ↓H␈↓Flow Chart Functions␈↓ ε(␈↓εDraft␈↓␈↓ H


␈↓ ↓H␈↓α␈↓ ∧λTHE BLOB FUNCTIONS OF FLOW CHARTS

␈↓ ↓H␈↓␈↓ α_When␈αone␈α
 studies␈αprograms␈α
organized␈α as␈α
flow␈αcharts,␈α
 one␈αis␈α
inclined␈αto␈α
prefer␈αflow␈α
charts
␈↓ ↓H␈↓with␈αa␈αsingle␈αentry␈αand␈αa␈αsingle␈αexit.␈α However,␈αthe␈αoperations␈αof␈αbuilding␈αflow␈αcharts␈αfrom␈αparts
␈↓ ↓H␈↓inevitably involve flow charts with multiple entries and multiple exits.

␈↓ ↓H␈↓␈↓ α_Our␈α approach␈α is␈α to␈α characterize␈αflow␈α charts␈α by␈α certain␈αfunctions,␈αcalled␈α␈↓↓blob␈αfunctions␈↓,
␈↓ ↓H␈↓and␈αshow␈αhow␈αto␈αget␈α the␈αfunctions␈αcharacterizing␈αnew␈αflow␈αcharts␈αfrom␈αthose␈αcharacterizing␈α the
␈↓ ↓H␈↓flow␈α∂charts␈α∞from␈α∂which␈α∞ the␈α∂new␈α∞ones␈α∂are␈α∞formed.␈α∂  This␈α∞is␈α∂in␈α∞contrast␈α∂with␈α∞ the␈α∂approach␈α∞of
␈↓ ↓H␈↓Ianov␈αas␈αdescribed␈αin␈α(Ianov␈α1959)␈α and␈α(Rutledge␈α1964)␈αwho␈αwork␈αdirectly␈αwith␈αthe␈α
flow␈αcharts.
␈↓ ↓H␈↓Our␈α∃reason␈α∃is␈α⊗ that␈α∃mathematics␈α∃ provides␈α∃ us␈α⊗  with␈α∃ powerful␈α∃ tools␈α⊗  for␈α∃ manipulating
␈↓ ↓H␈↓functions,␈α∞ and,␈α∞moreover,␈α∂facts␈α∞ about␈α∞flow␈α∞charts␈α∂ must␈α∞be␈α∞combined␈α∞with␈α∂other␈α∞mathematical
␈↓ ↓H␈↓facts which are most conveniently decribed in terms of functions, predicates and sets.










␈↓ ↓H␈↓␈↓ ε⊃Figure 1


␈↓ ↓H␈↓α1. Blob functions

␈↓ ↓H␈↓␈↓ α_Figure␈α1a␈αrepresents␈αa␈αflow␈αchart␈αor␈α␈↓↓blob␈↓␈α␈↓↓c␈↓␈αwhose␈αinner␈αworkings␈αwe␈αdo␈αnot␈αwish␈αto␈αspecify,
␈↓ ↓H␈↓but␈α∂whose␈α⊂behavior␈α∂we␈α⊂wish␈α∂to␈α⊂characterize␈α∂by␈α∂functions.␈α⊂ The␈α∂arrows␈α⊂into␈α∂the␈α⊂␈↓↓blob␈↓␈α∂represent
␈↓ ↓H␈↓paths␈α
along␈α
which␈αcontrol␈α
enters␈α
the␈α
flow␈αchart␈α
(called␈α
entries),␈α
and␈αthe␈α
arrows␈α
out␈αrepresent␈α
paths
␈↓ ↓H␈↓by␈αwhich␈αcontrol␈αleaves␈αit␈α(called␈α␈↓↓exits).␈↓␈α Let␈α␈↓↓En(c)␈↓␈αbe␈αthe␈αset␈αof␈αentries␈αof␈α␈↓↓c,␈↓␈αand␈αlet␈α␈↓↓Ex(c)␈↓␈αbe␈αits
␈↓ ↓H␈↓set␈α∞of␈α∞exits.␈α∞ Let␈α∞␈↓↓x␈↓␈α∞represent␈α∞the␈α∞state␈α∂vector,␈α∞i.e.␈α∞ the␈α∞collection␈α∞of␈α∞assignments␈α∞of␈α∞values␈α∂to␈α∞the
␈↓ ↓H␈↓variables␈αoccurring␈α
in␈αthe␈α
program.␈α We␈α
define␈αpredicates␈α
␈↓↓p␈↓βij␈↓↓(x,c)␈↓␈αwhere␈α
␈↓↓i␈↓␈αranges␈α
over␈α␈↓↓En(c)␈↓␈αand␈α
␈↓↓j␈↓
␈↓ ↓H␈↓ranges over ␈↓↓Ex(c)␈↓, and functions ␈↓↓s␈↓βi␈↓␈↓↓(x,c)␈↓ where ␈↓↓i␈↓ again ranges over ␈↓↓En(c)␈↓ as follows:

␈↓ ↓H␈↓␈↓ α_(i)␈α␈↓↓p␈↓βij␈↓␈↓↓(x,c)␈↓␈αis␈α true␈αif␈αand␈α only␈αif␈αentering␈αthe␈α flow␈αchart␈α␈↓↓c␈↓␈α at␈αentry␈α␈↓↓i␈↓␈α with␈αinitial␈α
state␈α ␈↓↓x␈↓
␈↓ ↓H␈↓results in  leaving the flow chart at exit ␈↓↓j␈↓.

␈↓ ↓H␈↓␈↓ α_(ii)␈α␈↓↓s␈↓βi␈↓␈↓↓(x,c)␈↓␈αis␈αthe␈αvalue␈αof␈αthe␈αstate␈αat␈αexit␈αfrom␈α the␈αflow␈αchart␈αwhen␈αit␈αis␈αentered␈αat␈α␈↓↓i␈↓␈αwith
␈↓ ↓H␈↓initial state ␈↓↓x.␈↓  Note that the ␈↓↓s␈↓βi␈↓'s are partial functions, because the program may never exit.

␈↓ ↓H␈↓␈↓ α_Obviously␈α
the␈α
predicates␈α
␈↓↓p␈↓βij␈↓␈α∞and␈α
the␈α
functions␈α
␈↓↓s␈↓βi␈↓␈α
characterize␈α∞the␈α
flow␈α
chart␈α
␈↓↓c,␈↓␈α∞because␈α
if
␈↓ ↓H␈↓one␈αknows␈α
these,␈αone␈α
knows␈αwhere␈α
the␈αprogram␈α
 will␈αexit␈α
and␈αwhat␈α
 the␈αnew␈α
state␈αwill␈α
 be␈αfor␈α
any
␈↓ ↓H␈↓entrance into the flow chart.

␈↓ ↓H␈↓␈↓ α_If␈α⊂ we␈α⊂suppose␈α⊂that␈α⊂the␈α⊂flow␈α⊂ chart␈α⊂is␈α⊂ultimately␈α⊂constructed␈α⊂out␈α⊂of␈α⊃elementary␈α⊂compute
␈↓ ↓H␈↓blocks␈α
and␈α
elementary␈α∞ decision␈α
blocks␈α
as␈α∞in␈α
Figure␈α
1b,␈α
one␈α∞needs␈α
to␈α
show␈α∞how␈α
to␈α
write␈α∞the␈α
␈↓↓p␈↓'s
␈↓ ↓H␈↓and␈α
␈↓↓s␈↓'s␈α∞for␈α
these␈α
elements␈α∞and␈α
then␈α∞ how␈α
to␈α
 get␈α∞the␈α
 ␈↓↓p␈↓'s␈α∞and␈α
 ␈↓↓s␈↓'s␈α
for␈α∞ a␈α
combination␈α∞ of␈α
blocks
␈↓ ↓H␈↓Flow Chart Functions␈↓ ε(␈↓εDraft␈↓␈↓ 91


␈↓ ↓H␈↓from␈α
 those␈αof␈α
 its␈α parts.␈α
  The␈αfirst␈α
 part␈αis␈α
 trivial.␈α  A␈α
compute␈αblock␈α
 has␈αjust␈α
one␈α
entry␈αand
␈↓ ↓H␈↓one␈αexit,␈α so␈αthere␈αis␈αjust␈αone␈α␈↓↓p␈↓␈αand␈αit␈αis␈αidentically␈α true,␈αand␈αthere␈αis␈α just␈αone␈α␈↓↓s,␈↓␈αand␈αit␈α is␈αjust
␈↓ ↓H␈↓the␈α function␈α
of␈αstate␈α
computed␈α by␈αthe␈α
block.␈α  A␈α
decision␈αblock␈αhas␈α
one␈α entry␈α
and␈αtwo␈αexits␈α
and
␈↓ ↓H␈↓the␈α
one␈α
␈↓↓p␈↓␈αis␈α
just␈α
the␈αpredicate␈α
for␈α
the␈αYES␈α
decision␈α
and␈αthe␈α
other␈α
is␈αthe␈α
predicate␈α
 for␈α
the␈αNO
␈↓ ↓H␈↓decision.  There is one ␈↓↓s,␈↓ and it is the identity function.
␈↓ ↓H␈↓Flow Chart Functions␈↓ ε(␈↓εDraft␈↓␈↓ 92


␈↓ ↓H␈↓␈↓ α_We introduce the following operations that give new charts from old ones:




















␈↓ ↓H␈↓␈↓ ε⊃Figure 2

␈↓ ↓H␈↓␈↓ α_(i)␈α∂Suppression␈α∂of␈α∂an␈α∂entry␈α∂␈↓↓i␈↓β0␈↓␈α∂ from␈α∂a␈α∂chart␈α∂␈↓↓c␈α∂(see␈↓␈α∂Figure␈α∂2a).␈α∂  This␈α∂gives␈α∂a␈α⊂new␈α∂chart
␈↓ ↓H␈↓␈↓↓suppress(c,i␈↓β0␈↓↓)␈↓␈α
with␈α
one␈α
fewer␈αentry,␈α
 and␈α
whose␈α
␈↓↓p␈↓'s␈αand␈α
␈↓↓s␈↓'s␈α
 are␈α
the␈αsame␈α
as␈α
before␈α
except␈αthat␈α
the
␈↓ ↓H␈↓subscript ␈↓↓i␈↓β0␈↓ is omitted.

␈↓ ↓H␈↓␈↓ α_(ii)␈α⊂Adjoining␈α∂two␈α⊂charts␈α∂␈↓↓c1␈↓␈α⊂and␈α∂ ␈↓↓c2␈↓␈α⊂side␈α⊂by␈α∂side␈α⊂(see␈α∂Figure␈α⊂2b).␈α∂ Call␈α⊂ the␈α⊂new␈α∂ chart
␈↓ ↓H␈↓␈↓↓adjoin(c1,c2)␈↓.␈α
  We␈α
 have␈α
␈↓↓En(adjoin(c1,c2))␈α
 =␈α
En(c1)␈α∪␈α
En(c2)␈↓,␈α
 and␈α
␈↓↓Ex(adjoin(c1,c2))␈α
=␈α
Ex(c1)␈α∪
␈↓ ↓H␈↓↓Ex(c2)␈↓.  Moreover, we have

␈↓ ↓H␈↓1)␈↓ α8␈α∞ ␈↓↓p␈↓βij␈↓↓(x,adjoin(c1,c2))␈α∞=␈α
␈↓αif␈↓↓␈α∞i␈α∞ε␈α
c1␈α∞␈↓αthen␈↓↓␈α∞(␈↓αif␈↓↓␈α∞j␈α
ε␈α∞c1␈α∞␈↓αthen␈↓↓␈α
p␈↓βij␈↓↓(x,c1)␈α∞␈↓αelse␈↓↓␈α∞␈↓αfalse␈↓↓)␈α
 ␈↓αelse␈↓↓␈α∞(␈↓αif␈↓↓␈α∞j␈α∞ε␈α
c1
␈↓ ↓H␈↓↓␈↓αthen␈↓↓ ␈↓αfalse␈↓↓ ␈↓αelse␈↓↓ p␈↓βij␈↓↓(x,c2))␈↓,

␈↓ ↓H␈↓and

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓s␈↓βi␈↓↓(x,adjoin(c1,c2))  =  ␈↓αif␈↓↓  i  ε c1  ␈↓αthen␈↓↓  s␈↓βi␈↓↓(x,c1) ␈↓αelse␈↓↓ p␈↓βi␈↓↓(x,c2)␈↓.

␈↓ ↓H␈↓Both of these are trivial operations but the next is not.

␈↓ ↓H␈↓␈↓ α_(iii)␈α∞Connecting␈α
 the␈α∞exit␈α∞ ␈↓↓m␈↓␈α
 to␈α∞the␈α
 entry␈α∞ ␈↓↓n␈↓␈α∞giving␈α
a␈α∞ new␈α
chart␈α∞ ␈↓↓loop(c,m,n)␈↓␈α∞with␈α
 one
␈↓ ↓H␈↓fewer  exit (see Figure 2c).  The new ␈↓↓p␈↓'s and ␈↓↓s␈↓'s are defined by the recursion equations

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓p␈↓βij␈↓↓(x,loop(c,m,n)) ← p␈↓βij␈↓↓(x,c) ∨ (p␈↓βim␈↓↓(x,c) ∧ p␈↓βnj␈↓↓(s␈↓βi␈↓↓(x,c),loop(c,m,n)))␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓4)␈↓ α8  ␈↓↓s␈↓βi␈↓↓(x,loop(c,m,n)) ← ␈↓αif␈↓↓ ¬p␈↓βim␈↓↓(x,c) ␈↓αthen␈↓↓ s␈↓βi␈↓↓(x,c) ␈↓αelse␈↓↓ s␈↓βn␈↓↓(s␈↓βi␈↓↓(x,c),loop(c,m,n))␈↓.
␈↓ ↓H␈↓Flow Chart Functions␈↓ ε(␈↓εDraft␈↓␈↓ 93


␈↓ ↓H␈↓␈↓ α_A␈αlittle␈αcontemplation␈αwill␈αshow␈αthat␈αthis␈αrecursive␈αprocess␈αcaptures␈αour␈αintuitive␈α
notion␈αof
␈↓ ↓H␈↓what happens when an exit is connected to an entry.

␈↓ ↓H␈↓␈↓ α_It␈αis␈αevident␈αthat␈αany␈αflow␈αchart␈α
can␈αbe␈αbuilt␈αfrom␈αelementary␈αcompute␈αblocks␈αand␈α
tests␈αby
␈↓ ↓H␈↓these␈α∃operations,␈α∀and␈α∃furthermore␈α∃any␈α∀two␈α∃flow␈α∀charts␈α∃can␈α∃be␈α∀glued␈α∃together␈α∃using␈α∀these
␈↓ ↓H␈↓operations.

␈↓ ↓H␈↓␈↓ α_An␈α⊂objective␈α∂worth␈α⊂undertaking␈α⊂is␈α∂to␈α⊂show␈α⊂that␈α∂any␈α⊂two␈α⊂equivalent␈α∂flow␈α⊂charts␈α⊂can␈α∂be
␈↓ ↓H␈↓proved␈α∂equivalent␈α∂by␈α⊂the␈α∂theory␈α∂of␈α∂recursively␈α⊂defined␈α∂functions␈α∂from␈α∂these␈α⊂definitions.␈α∂ This
␈↓ ↓H␈↓would␈α⊂be␈α⊂the␈α⊂analog␈α⊂of␈α⊃Ianov's␈α⊂theorem␈α⊂and␈α⊂ought␈α⊂to␈α⊃be␈α⊂based␈α⊂on␈α⊂a␈α⊂decision␈α⊃procedure␈α⊂for
␈↓ ↓H␈↓recursions␈α
(possibly␈α
restricted␈αto␈α
iterative␈α
form)␈α
where␈αthere␈α
is␈α
only␈αone␈α
variable.␈α
 It␈α
would␈αhave
␈↓ ↓H␈↓the␈αadvantage␈αover␈αthe␈αIanov␈αtheory␈αthat␈αit␈α
is␈αsimply␈αthe␈αtheory␈αof␈αrecursion␈αequations␈αapplied␈α
to
␈↓ ↓H␈↓this case rather than an ad hoc confection.

␈↓ ↓H␈↓␈↓ α_I␈α
don't␈α
know␈α
such␈α
a␈α
decision␈α
procedure,␈αnor␈α
has␈α
there␈α
been␈α
formulated␈α
a␈α
theory␈αof␈α
recursion
␈↓ ↓H␈↓equations that is proved complete for this case.

␈↓ ↓H␈↓Note of February 19, 1977:

␈↓ ↓H␈↓␈↓ α_The␈α⊂recursion␈α∂involved␈α⊂when␈α∂an␈α⊂exit␈α∂is␈α⊂connected␈α∂to␈α⊂an␈α∂entry␈α⊂can␈α∂be␈α⊂represented␈α⊂by␈α∂a
␈↓ ↓H␈↓␈↓↓functional equation␈↓ and a ␈↓↓minimization schema␈↓ as discussed in (McCarthy 1977).

␈↓ ↓H␈↓␈↓ α_If␈αtwo␈αexits␈αof␈αa␈αchart␈αare␈αconnected␈αto␈αtwo␈αentries,␈αthis␈αcan␈αbe␈αdone␈αin␈αtwo␈αdifferent␈α
orders
␈↓ ↓H␈↓-␈αthus␈αgiving␈αrise␈αto␈αtwo␈αsets␈αof␈αrecursions␈αfor␈αthe␈αnew␈αchart.␈α Moreover,␈αa␈αthird␈αset␈αof␈αrecursions
␈↓ ↓H␈↓can␈αbe␈αobtained␈αby␈αdoing␈αthe␈αconnections␈αsimultaneously.␈α It␈αshould␈αbe␈αpossible␈αto␈αshow␈αfrom␈αthe
␈↓ ↓H␈↓␈↓↓functional␈α⊃equations␈↓␈α⊃and␈α⊃␈↓↓minimization␈α⊃schemas␈↓␈α⊃of␈α⊂these␈α⊃recursions␈α⊃that␈α⊃the␈α⊃same␈α⊃funtions␈α⊂are
␈↓ ↓H␈↓obtained.




␈↓ ↓H␈↓αREFERENCES

␈↓ ↓H␈↓␈↓αIanov,␈α
Y.I.␈↓␈α
(1960):␈α
"The␈α
Logical␈α
Schemes␈α
of␈α
Algorithms",␈α
in␈α
␈↓↓␈α
Problems␈α
of␈α
Cybernetics␈↓,␈α
vol.1,␈αpp.␈α
82-
␈↓ ↓H␈↓140, Pergamon Press, New York (English Translation).

␈↓ ↓H␈↓␈↓αRutledge, J.D.␈↓ (1964): "On Ianov's Program Schemata", ␈↓↓J. ACM␈↓, ␈↓α11␈↓(1): 1-9 (January).


␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of BLOB[W76,JMC] PUBbed at 12:45 on February 19, 1977.␈↓